The present invention relates to a program translation method for compiling a source program of a computer language into an object program.
A procedure for translating a program in a FORTRAN compiler is represented as shown in FIG. 2. Namely, a lexical/syntax analysis is conducted on a source program 201 to transform the source program into a first program 203 of an intermediate language suitable for the processing of the compiler (step 202), and then an optimization is accomplished on the first program 203 of the intermediate language so as to increase the execution performance of the object program thereof, thereby generating a second program 205A of the intermediate language (step 204A). Thereafter, the second program 205A of the intermediate language is translated into an object program 207A executable in a computer (step 206).
The optimization processing 204A is achieved as briefly illustrated in FIG. 3. That is, a control flow analysis processing (step 301) is first executed to obtain control flow data 305 representing the sequence of execution of the components included in the intermediate language program 203 (step 301). Next, a dataflow analysis processing is executed to obtain, by use of the control flow data 305, dataflow data 306A representing the relationships between definitions and uses of variables (step 302A). Thereafter, a program transformation processing is executed to transform the intermediate language program 203 by use of the control flow data 305 and the dataflow data 306A and to output an intermediate language program 205A corresponding to the object program 207A having an improved execution efficiency.
As a kind of the dataflow data 306, there exist data of relationships between definitious and uses of (simple) variables and arrays (i.e. reaching definitions, ud-chains, du-chains, flow dependences, and the like).
A method for analyzing the relationship between definitions and codes of variables has been described in the following reference (1).
(1) Aho, Ullman: Principles of Compiler Design, Addison-Wesly (1977), pp. 478-480.
A method for analyzing the control flow has also been described in the reference (1).
On the other hand, a method for analyzing the relationships between definitions and uses of arrays has been described in reference (2).
(2) 3rd USA-Japan Computer Conference, pp. 273-279 (1978).
In addition, a method for transforming a program by use of the data of relationships between definitions and uses (flow dependences) has been described in the following reference (3).
(3) 8th Conference on Principles of Programming Languages, Association for Computing Machinery, pp. 207-218 (1981).
The method of the reference (1) above for analyzing the definition/use relationships is a method associated with variables; however, this method cannot be applied to the definition/use relationships of array references because of the following reason. Namely, although a reference to a variable at a point of a program always indicates a fixed address, a reference to an array element at a point of a program indicates an address which changes depending on a subscript thereof.
On the other hand, the method of the reference (2) for analyzing the definition/use relationship is a method associated with array references; however, this method is attended with a disadvantage that when a loop includes a conditional statement, an appropriate dataflow data essential for the optimization cannot be attained in some cases.
The disadvantage will be described by use of FIG. 4. The diagram illustrates a program 401 written in FORTRAN. This source program can be transformed or vectorized into an object program executable in a supercomputer such as Cray-1, S-810 of Hitachi, or the like, which enables to execute the program at a speed considerably higher than that developed in a general purpose computer. This is because the program 401 does not include a definition/use relationship unsuitable for the vectorization, namely, which cannot be vectorized without changing the result of the program execution.
The definition/use relationship not suitable for the vectorization will be here described with reference to FIG. 10. Assume that there exist a first statement including a first definition d1 of an array or a variable and a first use u1 thereof and a second statement 902 including a second definition d2 of an array or a variable and a second use d2 thereof and that there exist a definition/use relationship from the first definition d1 to the second use u2 and a definition/use relationship from the second definition d2 to the first use u1. With such cyclic definition/use relationships, even when the statements in a loop are arbitrarily reordered, the result of the execution of the vectorized program cannot be matched with that of the original program, which has been well known and has been discussed in the reference (3).
In the program 401, the problem to be solved to determine whether or not the vectorization is applicable is the relationship between the array definition statement d3 and the array use statement u. Namely, if the value of data defined by the array definition statement d3 is used by the array use statement u, there appears a cyclic definition/use relationship and the program is hence unsuitable for a vectorization, namely, the program cannot be transformed into a program executable in a supercomputer. However, since the value of data defined by the array definition statement d3 is changed by use of the array definition statements d1 and d2, it is not possible that the value is used by the array use statement u. Consequently, the program 401 does not contain a definition/use relationship unsuitable for the vectorization.
However, according to the analysis method of the definition/use relationships described in the reference (2), the relationship between the array definition statement d3 and the array use statement u is assumed to be unsuitable for the vectorization, and hence the program 401 cannot be subjected to a vectorization. The relationship is regarded as unsuitable for the vectorization because of the following reason. According to the analysis method of the definition/use relationships described in the reference (2), when the relationship between the array definition statement d3 and the array use statement u is checked, the presence or absence of the definition/use relationship is judged only by comparing the subscripts of the array definition and the array use. Namely, the array definition statement d1 and the array definition statement d2 are not taken into consideration. As a result, the value of data defined by the array definition statement d3 is assumed to be possibly used by the array use statement u. However, this relationship is not suitable for the vectorization.
If the definition/use relationships are checked for a program with a DO loop not having a conditional statement or such a statement effectively similar thereto, the appropriate definition/use relationships can be attained through a relatively easy procedure for examining the subscripts of the array definition statements other than the array definition statement for which the relationship is to be determined. However, if a conditional statement is contained like in the case of the program 401, this procedure cannot be used to determine the relationship. This is because the following two cases cannot be discriminated.
The first case is a case like the program 401. That is, in all paths from the first step of the DO loop to the array use statement to be subjected to the judgment of the definition/use relationship, namely, in the case of the program 401, there exists an array definition statement having a subscript I in the path passing THEN side of the conditional control structure from the IF statement 411 to the END IF statement 412, which passes the array definition statement d1 and in the path passing ELSE side of the conditional control structure, which passes the array definition statement d2; consequently, the value of data defined by the array definition statement d3 does not reach the array use statement u.
In contrast, the second case includes a path not having an array definition statement, and hence the value of the data defined by the array definition statement actually reaches the array use statement. For example, in a program generated by removing the array definition statement d2 from the program 401, the value defined by the array definition statement d3 reaches the array use statement u.